//package core.src.main.java.com.gameai.tickettoride.core;
package com.gameai.tickettoride.core;
import static com.gameai.tickettoride.core.Graph.standardDeviation;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;

public class Graph {
    
  public ArrayList<Player> player_list = new ArrayList<Player>();
    
  public City Vancouver, Calgary, Winnepeg, SaultStMarie, Montreal, Seattle, Helena, Duluth, Toronto, Boston, Portland, Omaha, Chicago, Pittsburgh, NewYork,
  SaltLake, Denver, Kansas,StLouis, Nashville,Raleigh,Washington,SanFrancisco, LasVegas, SantaFe, Oklahoma, LittleRock, Atlanta, Charleston,
  LosAngeles, Phoenix, ElPaso, Dallas, Houston, NewOrleans, Miami;
  
  public Rail TorontoToChicago, OklahomaCityToDenver, DenverToHelena, ChicagoToDuluth, TorontoToPittsburgh, VancouverToCalgary, VancouverToSeattle, CalgaryToSeattle,CalgaryToWinnepeg,CalgaryToHelena,WinnepegToHelena,WinnepegToDuluth,WinnepegToSaultStMarie,
  SaultStMarieToMontreal,MontrealToBoston,MontrealToToronto, MontrealToNewYork, TorontoToDuluth,TorontoToSaultStMarie,SaultStMarieToDuluth, DuluthToHelena,
  HelenaToSeattle,SeattleToPortland, PortlandToSaltLake, PortlandToSanFran, SanFranToLosAngeles, LosAngelesToLasVegas, LasVegasToSaltLake,
  SaltLakeToHelena, HelenaToOmaha, SaltLakeToDenver, DenverToOmaha, OmahaToDuluth,OmahaToChicago,ChicagoToPittsburgh, NewYorkToBoston, NewYorkToPittsburgh,
  NewYorkToWashington, PittsburghToWashington, WashingtonToRaleigh, RaleighToNashville,RaleighToPittsburgh,PittsburghToStLouis, ChicagoToStLouis, StLouisToKansasCity, KansasCityToOmaha,OmahaToDenver,KansasCityToDenver,
  DenverToPhoenix, DenverToSantaFe, SantaFeToPhoenix, SantaFeToElPaso,ElPasoToLosAngeles,ElPasoToHouston,ElPasoToDallas, SantaFeToOklahomaCity, 
  OklahomaCityToKansasCity, ElPasoToOklahomaCity, OklahomaCityToDallas, OklahomaCityToLittleRock, LittleRockToDallas, DallasToHouston, HoustonToNewOrleans,
  LittleRockToNewOrleans, NewOrleansToAtlanta, NewOrleansToMiama, AtlantaToMiami,MiamiToCharleston, AtlantaToCharleston, CharlestonToRaleigh, AtlantaToRaleigh,
  RaleighToWashington, AtlantaToNashville,NashvilleToLittleRock, NashvilleToStLouis, NashvilleToPittsburgh, SanFranToSaltLake, LosAngelesToPhoenix, LittleRockToStLouis;
  
  //\s=\s\{\w+\,\w+\}
  
  City[] AM; City[] ANe; City[] ANa; City[] AR; City[] AC;
  City[] CM; City[] CR; City[] CN; City[] NH; City[] NL;
  City[] NM; City[] HE; City[] HD; City[] DE; City[] EL;
  City[] EP;  City[] ES; City[] EO; City[] ODa; City[] OS;
  City[] OK; City[] OL; City[] ODe; City[] DL; City[] LN;
  City[] LS; City[] NR; City[] RW; City[] RP; City[] WP;
  City[] PS; City[]  SN; City[] SK; City[] PNa; City[] PC;
  City[] PNe; City[] PT; City[] WN; City[]  NB; City[]  BM;
  City[] MN; City[]  MT; City[]  MS; City[]  TC;  City[]  TS;
  City[] TD; City[]  SD; City[]  DO; City[]  DH; City[]  DW;
  City[] KO; City[]  KD; City[]  DS; City[]  DeH; City[]  DeO;
  City[] DeS; City[]  DP; City[]  SL; City[]  LL; City[]  LSa;
  City[] SP; City[]  PSe; City[]  SeV; City[]  SS; City[]  SaP;
  City[] SaH; City[]  HS; City[]  HC; City[]  CS; City[]  CV;
  City[] CW; City[]  WH; City[]  WD; City[]  ChS; City[]  CO; City[] HO;
  City[] CD; City[] SPo; City[] WSa; City[] LP;
  
 

  public static enum COLOR {gray, red, pink, orange, yellow, green, blue, black, white};

  public static int[] SCORES = {0,1,2,4,7,10,15};
  
  private Map<City[],Rail> connections; 
  public City[] Cities;
  public Rail[] Rails;
  
  public Graph() {
      connections = new HashMap<City[],Rail>();
          
      Vancouver = new City(); Calgary = new City();  Winnepeg = new City(); SaultStMarie = new City(); Montreal = new City(); Seattle = new City();  Helena = new City(); Duluth = new City(); Toronto = new City(); Boston= new City();Portland= new City();Omaha= new City(); Chicago = new City(); Pittsburgh= new City(); NewYork = new City();
      SaltLake = new City();Denver = new City(); Kansas = new City(); StLouis= new City();Nashville= new City();Raleigh= new City();Washington= new City();SanFrancisco= new City();LasVegas= new City();SantaFe= new City();Oklahoma= new City();LittleRock= new City();Atlanta= new City();Charleston = new City();
      LosAngeles = new City();Phoenix = new City();ElPaso= new City();Dallas= new City();Houston= new City();NewOrleans= new City();Miami= new City();

    VancouverToCalgary = new Rail(); VancouverToSeattle = new Rail(); CalgaryToSeattle = new Rail();CalgaryToWinnepeg = new Rail();CalgaryToHelena = new Rail();WinnepegToHelena = new Rail();WinnepegToDuluth = new Rail();WinnepegToSaultStMarie = new Rail();
    SaultStMarieToMontreal = new Rail();MontrealToBoston = new Rail();MontrealToToronto = new Rail();MontrealToNewYork = new Rail();TorontoToDuluth = new Rail();TorontoToSaultStMarie = new Rail();SaultStMarieToDuluth = new Rail(); DuluthToHelena = new Rail();
    HelenaToSeattle = new Rail();SeattleToPortland = new Rail(); PortlandToSaltLake = new Rail();PortlandToSanFran = new Rail(); SanFranToLosAngeles = new Rail(); LosAngelesToLasVegas = new Rail(); LasVegasToSaltLake = new Rail();
    SaltLakeToHelena = new Rail(); HelenaToOmaha = new Rail(); SaltLakeToDenver = new Rail();DenverToOmaha = new Rail();OmahaToDuluth = new Rail();OmahaToChicago = new Rail();ChicagoToPittsburgh = new Rail(); NewYorkToBoston = new Rail(); NewYorkToPittsburgh = new Rail();
    NewYorkToWashington = new Rail(); PittsburghToWashington = new Rail();WashingtonToRaleigh = new Rail(); RaleighToNashville = new Rail();RaleighToPittsburgh = new Rail();PittsburghToStLouis = new Rail(); ChicagoToStLouis = new Rail(); StLouisToKansasCity = new Rail(); KansasCityToOmaha = new Rail();OmahaToDenver = new Rail();KansasCityToDenver = new Rail();
    DenverToPhoenix = new Rail(); DenverToSantaFe = new Rail();SantaFeToPhoenix = new Rail();SantaFeToElPaso = new Rail();ElPasoToLosAngeles = new Rail();ElPasoToHouston = new Rail();ElPasoToDallas = new Rail(); SantaFeToOklahomaCity = new Rail(); 
    OklahomaCityToKansasCity = new Rail();ElPasoToOklahomaCity = new Rail();OklahomaCityToDallas = new Rail(); OklahomaCityToLittleRock = new Rail();LittleRockToDallas = new Rail();DallasToHouston = new Rail();HoustonToNewOrleans = new Rail();
    LittleRockToNewOrleans = new Rail(); NewOrleansToAtlanta = new Rail(); NewOrleansToMiama = new Rail(); AtlantaToMiami = new Rail();MiamiToCharleston = new Rail(); AtlantaToCharleston = new Rail(); CharlestonToRaleigh = new Rail();AtlantaToRaleigh = new Rail();
    RaleighToWashington = new Rail(); AtlantaToNashville = new Rail();NashvilleToLittleRock = new Rail(); NashvilleToStLouis = new Rail(); NashvilleToPittsburgh = new Rail(); SanFranToSaltLake = new Rail(); LosAngelesToPhoenix = new Rail(); TorontoToPittsburgh = new Rail();
    ChicagoToDuluth = new Rail(); DenverToHelena = new Rail(); OklahomaCityToDenver = new Rail(); LittleRockToStLouis = new Rail(); TorontoToChicago = new Rail();
    
    AM = new City[]{Atlanta,Miami};  ANe = new City[]{Atlanta,NewOrleans};  ANa = new City[]{Atlanta,Nashville};  AR = new City[]{Atlanta,Raleigh};  AC = new City[]{Atlanta,Charleston};
    CM = new City[]{Charleston,Miami};  CR = new City[]{Charleston,Raleigh};  CN = new City[]{Charleston,NewOrleans};  NH = new City[]{NewOrleans,Houston};  NL = new City[]{NewOrleans,LittleRock};
    NM = new City[]{NewOrleans,Miami};  HE = new City[]{Houston, ElPaso};  HD = new City[]{Houston, Dallas};  DE = new City[]{Dallas, ElPaso};  EL = new City[]{ElPaso, LosAngeles};
    EP = new City[]{ElPaso,Phoenix};   ES = new City[]{ElPaso,SantaFe};  EO = new City[]{ElPaso,Oklahoma};  ODa = new City[]{Oklahoma,Dallas};  OS = new City[]{Oklahoma,SantaFe};
    OK = new City[]{Oklahoma,Kansas};  OL = new City[]{Oklahoma,LittleRock};  ODe = new City[]{Oklahoma,Denver};  DL = new City[]{Dallas,LittleRock};  LN = new City[]{LittleRock,Nashville};
    LS = new City[]{LittleRock,StLouis};  NR = new City[]{Nashville,Raleigh};  RW = new City[]{Raleigh,Washington};  RP = new City[]{Raleigh,Pittsburgh};  WP = new City[]{Washington,Pittsburgh};
    PS = new City[]{Pittsburgh,StLouis};   SN = new City[]{StLouis,Nashville};  SK = new City[]{StLouis,Kansas};  PNa = new City[]{Pittsburgh,Nashville};  PC = new City[]{Pittsburgh,Chicago};
    PNe = new City[]{Pittsburgh,NewYork};  PT = new City[]{Pittsburgh,Toronto};  WN = new City[]{Washington,NewYork};   NB = new City[]{NewYork,Boston};   BM = new City[]{Boston,Montreal};
    MN = new City[]{Montreal,NewYork};   MT = new City[]{Montreal,Toronto};   MS = new City[]{Montreal,SaultStMarie};   TC = new City[]{Toronto,Chicago};    TS = new City[]{Toronto,SaultStMarie};
    TD = new City[]{Toronto,Duluth};   SD = new City[]{SaultStMarie,Duluth};   DO= new City[]{Duluth,Omaha};   DH= new City[]{Duluth,Helena};   DW = new City[]{Duluth,Winnepeg};
    KO = new City[]{Kansas,Omaha};   KD = new City[]{Kansas,Denver};   DS = new City[]{Denver,SantaFe};   DeH = new City[]{Denver,Helena};   DeO = new City[]{Denver,Omaha};
    DeS= new City[]{Denver,SaltLake};   DP = new City[]{Denver,Phoenix};   SL = new City[]{SaltLake,LasVegas};   LL = new City[]{LasVegas,LosAngeles};   LSa = new City[]{LosAngeles,SanFrancisco};
    SP = new City[]{SanFrancisco,Portland};   PSe = new City[]{Portland,Seattle};   SeV = new City[]{Seattle,Vancouver};   SS = new City[]{SanFrancisco,SaltLake};   SaP= new City[]{SaltLake,Portland};
    SaH = new City[]{SaltLake,Helena};   HS = new City[]{Helena,Seattle};   HC = new City[]{Helena,Calgary};   CS = new City[]{Calgary,Seattle};   CV = new City[]{Calgary,Vancouver};
    CW = new City[]{Calgary,Winnepeg};   WH = new City[]{Winnepeg,Helena};   WD = new City[]{Winnepeg,Duluth};   ChS= new City[]{Chicago,StLouis};   CO = new City[]{Chicago,Omaha};  HO = new City[]{Helena,Omaha};
    CD= new City[]{Chicago,Duluth};  SPo = new City[]{SantaFe,Phoenix};  WSa = new City[]{Winnepeg, SaultStMarie}; LP = new City[]{LosAngeles, Phoenix};
            
    VancouverToCalgary.distance = 3; VancouverToCalgary.color = 0;
    VancouverToSeattle.distance = 1; VancouverToSeattle.dual = true; VancouverToSeattle.color = 0;
    CalgaryToSeattle.distance = 4; CalgaryToSeattle.color = 0;
    CalgaryToWinnepeg.distance = 6; CalgaryToWinnepeg.color = 8;
    CalgaryToHelena.distance = 4; CalgaryToHelena.color = 8;
    WinnepegToHelena.distance = 4;
    WinnepegToDuluth.distance = 4;
    WinnepegToSaultStMarie.distance = 6;
    SaultStMarieToMontreal.distance = 5;
    MontrealToBoston.distance = 2; MontrealToBoston.dual = true;
    MontrealToToronto.distance = 3;
    MontrealToNewYork.distance = 3;
    TorontoToDuluth.distance = 6;
    TorontoToSaultStMarie.distance = 2;
    SaultStMarieToDuluth.distance = 3;
    DuluthToHelena.distance = 6;
    HelenaToSeattle.distance = 6;
    SeattleToPortland.distance = 1; SeattleToPortland.dual = true;
    PortlandToSaltLake.distance = 6;
    PortlandToSanFran.distance = 5; PortlandToSanFran.dual = true;
    SanFranToLosAngeles.distance = 3; SanFranToLosAngeles.dual = true;
    LosAngelesToLasVegas.distance = 2; 
    LasVegasToSaltLake.distance = 3;
    SaltLakeToHelena.distance = 3; 
    HelenaToOmaha.distance = 5;
    SaltLakeToDenver.distance = 3; SaltLakeToDenver.dual = true;
    DenverToOmaha.distance = 4;
    OmahaToDuluth.distance = 2; OmahaToDuluth.dual = true;
    OmahaToChicago.distance = 4;
    ChicagoToPittsburgh.distance = 3; ChicagoToPittsburgh.dual = true;
    NewYorkToBoston.distance = 2; NewYorkToBoston.dual = true;
    NewYorkToPittsburgh.distance = 2; NewYorkToPittsburgh.dual = true;
    NewYorkToWashington.distance = 2; NewYorkToWashington.dual = true;
    PittsburghToWashington.distance = 2;
    WashingtonToRaleigh.distance = 2; WashingtonToRaleigh.dual = true;
    RaleighToNashville.distance = 3;
    RaleighToPittsburgh.distance = 2;
    PittsburghToStLouis.distance = 5;
    ChicagoToStLouis.distance = 2; ChicagoToStLouis.dual = true;
    StLouisToKansasCity.distance = 2; StLouisToKansasCity.dual = true;
    KansasCityToOmaha.distance  = 1; KansasCityToOmaha.dual = true;
    OmahaToDenver.distance = 4;
    KansasCityToDenver.distance = 4; KansasCityToDenver.dual = true;
    DenverToPhoenix.distance = 5;
    DenverToSantaFe.distance = 2;
    SantaFeToPhoenix.distance = 3;
    SantaFeToElPaso.distance = 2;
    ElPasoToLosAngeles.distance = 6;
    ElPasoToHouston.distance = 6;
    ElPasoToDallas.distance = 4;
    SantaFeToOklahomaCity.distance = 3; 
    OklahomaCityToKansasCity.distance = 2; OklahomaCityToKansasCity.dual = true;
    ElPasoToOklahomaCity.distance = 5;
    OklahomaCityToDallas.distance = 2; OklahomaCityToDallas.dual = true;
    OklahomaCityToLittleRock.distance = 2;
    LittleRockToDallas.distance = 2;
    DallasToHouston.distance = 1; DallasToHouston.dual = true;
    HoustonToNewOrleans.distance = 2;
    LittleRockToNewOrleans.distance = 3;
    NewOrleansToAtlanta.distance = 4; NewOrleansToAtlanta.dual = true;
    NewOrleansToMiama.distance = 6;
    AtlantaToMiami.distance = 5;
    MiamiToCharleston.distance = 4;
    AtlantaToCharleston.distance = 2;
    CharlestonToRaleigh.distance = 2;
    AtlantaToRaleigh.distance = 2; AtlantaToRaleigh.dual = true;
    RaleighToWashington.distance = 2; RaleighToWashington.dual = true;
    AtlantaToNashville.distance = 1;
    NashvilleToLittleRock.distance = 3;
    NashvilleToStLouis.distance = 2;
    NashvilleToPittsburgh.distance = 4;
    LosAngelesToPhoenix.distance = 3;
    TorontoToPittsburgh.distance = 2; TorontoToPittsburgh.color = 0;
    ChicagoToDuluth.distance = 3; ChicagoToDuluth.color = 1;
    SanFranToSaltLake.distance = 5; SanFranToSaltLake.color = 38; SanFranToSaltLake.dual = true;
    DenverToHelena.distance = 4; DenverToHelena.color = 5;
    OklahomaCityToDenver.distance = 4; OklahomaCityToDenver.color = 1;
    LittleRockToStLouis.distance = 2; LittleRockToStLouis.color = 0;
    TorontoToChicago.distance = 4; TorontoToChicago.color = 8;
    
    WinnepegToHelena.color = 6; WinnepegToDuluth.color = 7; WinnepegToSaultStMarie.color = 0;
    SaultStMarieToMontreal.color = 7; MontrealToBoston.color = 0; MontrealToToronto.color = 0; MontrealToNewYork.color = 8; TorontoToDuluth.color = 2;
    TorontoToSaultStMarie.color = 0; SaultStMarieToDuluth.color = 0; DuluthToHelena.color = 3; HelenaToSeattle.color = 4; SeattleToPortland.color = 0;
    PortlandToSaltLake.color = 6; PortlandToSanFran.color = 52;
    SanFranToLosAngeles.color = 42; LosAngelesToLasVegas.color = 0; LasVegasToSaltLake.color = 3;
    SaltLakeToHelena.color = 2; HelenaToOmaha.color = 1; SaltLakeToDenver.color = 41;DenverToOmaha.color = 2;OmahaToDuluth.color = 0;
    OmahaToChicago.color = 6; ChicagoToPittsburgh.color = 73; NewYorkToBoston.color = 41; NewYorkToPittsburgh.color = 58;
    NewYorkToWashington.color = 37; PittsburghToWashington.color = 0;WashingtonToRaleigh.color = 0; RaleighToNashville.color = 7;RaleighToPittsburgh.color = 0;
    PittsburghToStLouis.color = 5; ChicagoToStLouis.color = 58; StLouisToKansasCity.color = 26; KansasCityToOmaha.color = 00; OmahaToDenver.color = 2;
    KansasCityToDenver.color = 37; DenverToPhoenix.color = 8; DenverToSantaFe.color = 0;SantaFeToPhoenix.color = 0;SantaFeToElPaso.color = 0;
    ElPasoToLosAngeles.color = 7; ElPasoToHouston.color = 5;ElPasoToDallas.color = 1; SantaFeToOklahomaCity.color = 6; 
    OklahomaCityToKansasCity.color = 00;ElPasoToOklahomaCity.color = 4;OklahomaCityToDallas.color = 00; OklahomaCityToLittleRock.color = 0;
    LittleRockToDallas.color = 0;DallasToHouston.color = 00;HoustonToNewOrleans.color = 0;
    LittleRockToNewOrleans.color = 5; NewOrleansToAtlanta.color = 43; NewOrleansToMiama.color = 1; AtlantaToMiami.color = 6;MiamiToCharleston.color = 2;
    AtlantaToCharleston.color = 0; CharlestonToRaleigh.color = 0;AtlantaToRaleigh.color = 00;
    RaleighToWashington.color = 00; AtlantaToNashville.color = 0;NashvilleToLittleRock.color = 8; NashvilleToStLouis.color = 0; NashvilleToPittsburgh.color = 4;
    LosAngelesToPhoenix.color = 0;
    
    Vancouver.name = "Vancouver"; Calgary.name = "Calgary"; Winnepeg.name = "Winnepeg"; SaultStMarie.name = "SaultStMarie"; Montreal.name = "Montreal"; Seattle.name = "Seattle"; Helena.name = "Helena"; Duluth.name = "Duluth"; Toronto.name = "Toronto"; 
    Boston.name = "Boston"; Portland.name = "Portland"; Omaha.name = "Omaha"; Chicago.name = "Chicago"; Pittsburgh.name = "Pittsburgh"; NewYork.name = "NewYork";
    SaltLake.name = "SaltLake"; Denver.name = "Denver"; Kansas.name = "Kansas"; StLouis.name = "StLouis"; Nashville.name = "Nashville"; Raleigh.name = "Raleigh"; Washington.name = "Washington"; 
    SanFrancisco.name = "SanFrancisco"; LasVegas.name = "LasVegas"; SantaFe.name = "SantaFe"; Oklahoma.name = "Oklahoma"; LittleRock.name = "LittleRock"; Atlanta.name = "Atlanta"; Charleston.name = "Charleston";
    LosAngeles.name = "LosAngeles"; Phoenix.name = "Phoenix"; ElPaso.name = "ElPaso"; Dallas.name = "Dallas"; Houston.name = "Houston"; NewOrleans.name = "NewOrleans"; Miami.name = "Miami";
    
    connections.put(HC, CalgaryToHelena);connections.put(WH, WinnepegToHelena);connections.put(WD, WinnepegToDuluth);connections.put(WSa, WinnepegToSaultStMarie);
    connections.put(MS, SaultStMarieToMontreal);connections.put(BM, MontrealToBoston);connections.put(MT, MontrealToToronto);
    connections.put(MN, MontrealToNewYork);connections.put(TD, TorontoToDuluth);connections.put(TS, TorontoToSaultStMarie);
    connections.put(SD, SaultStMarieToDuluth);connections.put(DH, DuluthToHelena);connections.put(HS, HelenaToSeattle);
    connections.put(PSe, SeattleToPortland);connections.put(SaP, PortlandToSaltLake);connections.put(SP, PortlandToSanFran);connections.put(LSa, SanFranToLosAngeles);
    connections.put(LL, LosAngelesToLasVegas);connections.put(SL, LasVegasToSaltLake);connections.put(SaH, SaltLakeToHelena);connections.put(HO,HelenaToOmaha);
    connections.put(DeS, SaltLakeToDenver);connections.put(DeO, DenverToOmaha);connections.put(DO, OmahaToDuluth);connections.put(CO, OmahaToChicago);
    connections.put(PC, ChicagoToPittsburgh);connections.put(NB, NewYorkToBoston);connections.put(PNe, NewYorkToPittsburgh);
    connections.put(WN, NewYorkToWashington);connections.put(WP, PittsburghToWashington);connections.put(RW, WashingtonToRaleigh);
    connections.put(NR,  RaleighToNashville);connections.put(RP, RaleighToPittsburgh);connections.put(PS, PittsburghToStLouis);connections.put(ChS, ChicagoToStLouis);
    connections.put(SK, StLouisToKansasCity);connections.put(KO, KansasCityToOmaha);connections.put(DeO, OmahaToDenver);connections.put(KD, KansasCityToDenver);
    connections.put(DP, DenverToPhoenix);connections.put(DS, DenverToSantaFe);connections.put(SPo,SantaFeToPhoenix);connections.put(ES, SantaFeToElPaso);
    connections.put(EL, ElPasoToLosAngeles);connections.put(HE, ElPasoToHouston);connections.put(DE, ElPasoToDallas);connections.put(OS,SantaFeToOklahomaCity);
    connections.put(OK, OklahomaCityToKansasCity);connections.put(EO, ElPasoToOklahomaCity);connections.put(ODa, OklahomaCityToDallas);connections.put(OL,OklahomaCityToLittleRock);
    connections.put(DL, LittleRockToDallas);connections.put(HD,DallasToHouston);connections.put(NH, HoustonToNewOrleans);connections.put(NL, LittleRockToNewOrleans);
    connections.put(ANe, NewOrleansToAtlanta);connections.put(NM, NewOrleansToMiama);connections.put(AM, AtlantaToMiami);connections.put(CM, MiamiToCharleston);
    connections.put(AC,AtlantaToCharleston);connections.put(CR, CharlestonToRaleigh);connections.put(AR,AtlantaToRaleigh);connections.put(RW,RaleighToWashington);
    connections.put(ANa, AtlantaToNashville);connections.put(LN, NashvilleToLittleRock);connections.put( SN, NashvilleToStLouis); connections.put(LP, LosAngelesToPhoenix);
    connections.put(PNa, NashvilleToPittsburgh); connections.put(SeV, VancouverToSeattle); connections.put(CW ,CalgaryToWinnepeg);
    connections.put(CV, VancouverToCalgary); connections.put(PT, TorontoToPittsburgh); connections.put(CD, ChicagoToDuluth); connections.put(SS, SanFranToSaltLake);
    connections.put(DeH, DenverToHelena); connections.put(ODe, OklahomaCityToDenver); connections.put(LS, LittleRockToStLouis); connections.put(TC, TorontoToChicago);
    
    Cities = new City[]{Vancouver, Calgary, Winnepeg, SaultStMarie, Montreal, Seattle, Helena, Duluth, Toronto, Boston, Portland, Omaha, Chicago, Pittsburgh, NewYork,SaltLake, Denver, Kansas,StLouis, Nashville, Raleigh, Washington,SanFrancisco, LasVegas, SantaFe,Oklahoma,LittleRock,Atlanta,Charleston,LosAngeles, Phoenix, ElPaso, Dallas, Houston, NewOrleans, Miami};
    
    Rails = new Rail[]{DenverToHelena, VancouverToCalgary, VancouverToSeattle, CalgaryToSeattle,CalgaryToWinnepeg,CalgaryToHelena,WinnepegToHelena,WinnepegToDuluth,WinnepegToSaultStMarie,
    SaultStMarieToMontreal, MontrealToBoston, MontrealToToronto, MontrealToNewYork, TorontoToDuluth, TorontoToSaultStMarie, SaultStMarieToDuluth, DuluthToHelena,
    HelenaToSeattle,SeattleToPortland, PortlandToSaltLake,PortlandToSanFran, SanFranToLosAngeles, LosAngelesToLasVegas, LasVegasToSaltLake,
    SaltLakeToHelena, HelenaToOmaha, SaltLakeToDenver,DenverToOmaha,OmahaToDuluth,OmahaToChicago,ChicagoToPittsburgh, NewYorkToBoston, NewYorkToPittsburgh,
    NewYorkToWashington, PittsburghToWashington, WashingtonToRaleigh, RaleighToNashville, RaleighToPittsburgh, PittsburghToStLouis, ChicagoToStLouis, StLouisToKansasCity, KansasCityToOmaha,OmahaToDenver,KansasCityToDenver,
    DenverToPhoenix, DenverToSantaFe, SantaFeToPhoenix,SantaFeToElPaso,ElPasoToLosAngeles,ElPasoToHouston,ElPasoToDallas, SantaFeToOklahomaCity, 
    OklahomaCityToKansasCity, ElPasoToOklahomaCity, OklahomaCityToDallas, OklahomaCityToLittleRock, LittleRockToDallas,DallasToHouston,HoustonToNewOrleans,
    LittleRockToNewOrleans, NewOrleansToAtlanta, NewOrleansToMiama, AtlantaToMiami, MiamiToCharleston, AtlantaToCharleston, CharlestonToRaleigh,AtlantaToRaleigh, OklahomaCityToDenver,
    RaleighToWashington, AtlantaToNashville,NashvilleToLittleRock, NashvilleToStLouis, NashvilleToPittsburgh, SanFranToSaltLake, LosAngelesToPhoenix, TorontoToPittsburgh, ChicagoToDuluth, 
    LittleRockToStLouis, TorontoToChicago};
    
     //COUNT maxDEGREE OF EACH CITY FROM GRAPH REPRESENTATION
    int count = 0;
    
    for(City c : Cities){//for each city
      for(City[] ci : connections.keySet()){//go through the connections city[] list
        for(City cj : ci){//for each city[] in that list
          if(cj == c){//if it contains the city we're looking for
            count += Collections.frequency(connections.keySet (), ci); //add the number to the count
          }
        }//city[]
      }//[city[],...,]
      c.maxDegree = count;
    }//City
    
    //correct rail initial values
    for(Rail r : connections.values()){
      if (!r.dual){
        r.player = new Player[1];
      }
    }
    
//      Cities = new City[]{Vancouver, Calgary, Winnepeg, SaultStMarie, Montreal, Seattle, Helena, Duluth, Toronto, Boston, Portland, Omaha, Chicago, Pittsburgh, NewYork,
//      SaltLake, Denver, Kansas,StLouis, Nashville, Raleigh, Washington,SanFrancisco, LasVegas, SantaFe,Oklahoma,LittleRock,Atlanta,Charleston,
//      LosAngeles, Phoenix, ElPaso, Dallas, Houston, NewOrleans, Miami};
      
      
//      Rails = new Rail[]{DenverToHelena, VancouverToCalgary, VancouverToSeattle, CalgaryToSeattle,CalgaryToWinnepeg,CalgaryToHelena,WinnepegToHelena,WinnepegToDuluth,WinnepegToSaultStMarie,
//      SaultStMarieToMontreal, MontrealToBoston, MontrealToToronto, MontrealToNewYork, TorontoToDuluth, TorontoToSaultStMarie, SaultStMarieToDuluth, DuluthToHelena,
//      HelenaToSeattle,SeattleToPortland, PortlandToSaltLake,PortlandToSanFran, SanFranToLosAngeles, LosAngelesToLasVegas, LasVegasToSaltLake,
//      SaltLakeToHelena, HelenaToOmaha, SaltLakeToDenver,DenverToOmaha,OmahaToDuluth,OmahaToChicago,ChicagoToPittsburgh, NewYorkToBoston, NewYorkToPittsburgh,
//      NewYorkToWashington, PittsburghToWashington, WashingtonToRaleigh, RaleighToNashville, RaleighToPittsburgh, PittsburghToStLouis, ChicagoToStLouis, StLouisToKansasCity, KansasCityToOmaha,OmahaToDenver,KansasCityToDenver,
//      DenverToPhoenix, DenverToSantaFe, SantaFeToPhoenix,SantaFeToElPaso,ElPasoToLosAngeles,ElPasoToHouston,ElPasoToDallas, SantaFeToOklahomaCity, 
//      OklahomaCityToKansasCity, ElPasoToOklahomaCity, OklahomaCityToDallas, OklahomaCityToLittleRock, LittleRockToDallas,DallasToHouston,HoustonToNewOrleans,
//      LittleRockToNewOrleans, NewOrleansToAtlanta, NewOrleansToMiama, AtlantaToMiami, MiamiToCharleston, AtlantaToCharleston, CharlestonToRaleigh,AtlantaToRaleigh, OklahomaCityToDenver,
//      RaleighToWashington, AtlantaToNashville,NashvilleToLittleRock, NashvilleToStLouis, NashvilleToPittsburgh, SanFranToSaltLake, LosAngelesToPhoenix, TorontoToPittsburgh, ChicagoToDuluth, 
//      LittleRockToStLouis, TorontoToChicago}; 
    
      //City GUI x,y locations
      Vancouver.x = 240; Vancouver.y = 93; Seattle.x = 238; Seattle.y = 134; Portland.x = 222; Portland.y = 171;
      SanFrancisco.x = 211; SanFrancisco.y = 315; LosAngeles.x = 269; LosAngeles.y = 392; Calgary.x = 336; Calgary.y = 80;
      SaltLake.x = 357; SaltLake.y = 268; LasVegas.x = 316; LasVegas.y = 349; Phoenix.x = 357; Phoenix.y = 397; ElPaso.x = 444;
      ElPaso.y = 424; SantaFe.x = 448; SantaFe.y = 358; Denver.x = 453; Denver.y = 290; Helena.x = 410; Helena.y = 178; Winnepeg.x = 501; Winnepeg.y = 88;
      Dallas.x = 577; Dallas.y = 401; Houston.x = 607; Houston.y = 436; Oklahoma.x = 562; Oklahoma.y = 342; Kansas.x = 577; Kansas.y = 277;
      Omaha.x = 561; Omaha.y = 241; Duluth.x = 584; Duluth.y = 174; SaultStMarie.x = 677; SaultStMarie.y = 125; Chicago.x = 674; Chicago.y = 219;
      StLouis.x = 640; StLouis.y = 279; LittleRock.x = 629; LittleRock.y = 345; NewOrleans.x = 677; NewOrleans.y = 431; Miami.x = 839; Miami.y = 454;
      Atlanta.x = 746; Atlanta.y = 333; Nashville.x = 709; Nashville.y = 307; Charleston.x = 815; Charleston.y = 338; Raleigh.x = 794; Raleigh.y = 290;
      Washington.x = 837; Washington.y = 241; Pittsburgh.x = 769; Pittsburgh.y = 208; NewYork.x = 832; NewYork.y = 175; Toronto.x = 757; Toronto.y = 141;
      Boston.x = 870; Boston.y = 120; Montreal.x = 818; Montreal.y = 77;
  }
  
  public Map<City[],Rail> getConnections(){
      return connections;
  }
  
 
/**Top level A* method that takes in the potential cities and returns which the best one according to the destination
   * 
   * @param AIPlayer
   * @param destinations
   * @return
   */
    public City[] a_star_destination_select(int AIPlayer, City[] destinations){ 
    //for each city in the draw
    //evaluate for feasibility
    //take best
    int[] eval = new int[destinations.length];
    int[] best_list =  new int[destinations.length];
    City[] out = new City[destinations.length];
    
    int i = 0, best = 0, j = 0;

    for(City c : destinations){
      eval[i] = a_star_dest(c,AIPlayer);//ONLY USES AVAILABLE & CONNECTED CITIES
      
      if (best > eval[i]){
        best = eval[i];
        best_list[0] = i; 
      }
      i++;
    }
    
    i = 1;
    //throw out worst
    for(int value : eval){
      if(best == value && j == best_list[0]){
        continue;
      }
      //is this the single best, or are others also close?
      if(best < value+2*standardDeviation(eval) && best > value-2*standardDeviation(eval)){
        best_list[i] = j;
        j++;
        i++;
      }
    }
    return out;
  }
  
  /**Heuristic used in the A-star calculation. Calculates the ratio of total path length over city count for each destination city pair and
   * the city in question. Will produce lower values when the total rail path length is lower, relative to the city count.
   * 
   * @param city
   * @return
   */
  private int destination_factor(City city){
    //determine number of cities between this one and all destination citys
    //determine best route and find smallest distance from that route
    
    
    //get the list of cities in a players destination cards
    ArrayList<City[]> destination_list = new ArrayList<City[]>();
    ArrayList<Integer> shortest_count = new ArrayList<Integer>();
    ArrayList<Integer> shortest_length = new ArrayList<Integer>();
    ArrayList<Integer> d_factor = new ArrayList<Integer>();
    
    City[] route_d;
    Integer avg = 0;
    
    
    for(City[] di : destination_list){
      route_d = find_shortest_path(di);
      shortest_length.add(shortest_distance_length(route_d,city));
      shortest_count.add(shortest_distance(route_d, city));
    }
    
    for(int i = 0; i < shortest_length.size(); i++){
      d_factor.add(new Integer(shortest_length.get(i)/shortest_count.get(i)));
    }
   
    
    //GEOMETRIC average d_factor
    for(Integer xi : d_factor){
      avg = avg * xi;//Pi, 
    }
    avg = (int) Math.pow(avg, (1/(d_factor.size()+1)));//Nth root
    
    return avg;
  }
  /**
   * 
   * @param route
   * @param cj
   * @return shortest distance in rails that connects a city to a route
   */
 private Integer shortest_distance_length(City[] route, City cj ){
    ArrayList<City[]> routes = new ArrayList<City[]>(route.length);
    int i = 0, best = 100, best_index = 0;
    int pathlen = 0;
    City[] best_route;
    
    for(City ci : route){
      City[] path = new City[] {ci,cj};
      routes.add(i,find_shortest_path(path));
      i++;
    }
    
    i=0;
    for( City[] ri : routes){
      if (best > ri.length){
        best = ri.length;
        best_index = i;
        
      }
      i++;
    }
    
    best_route = routes.get(best_index);
    
    for(i = 0; i < best_route.length-1; i++){
      pathlen += getRailMappingAt(best_route[i],best_route[i+1]).distance;
    }
        
    return pathlen;    
  }
  /**
   * 
   * @param route
   * @param cj
   * @return the shortest path in cities that connects a city to a route
   */
  public Integer shortest_distance(City[] route, City cj ){
    int[] score = new int[route.length];
    int i = 0, best = 100, index = 0;
    
    for(City ci : route){
      City[] path = new City[] {ci,cj};
      score[i] = find_shortest_path(path).length;
      i++;
    }
    
    for( i = 0; i < score.length; i++){
      if (best > score[i]){
        best = score[i];
        index = i;//can be used to also return the city ci that is closest to cj
      }
    }
    
    return best;    
  }
  
  public static double mean(int[] data){
    int n = data.length; 
    if ( n < 2 ){ 
      return Double.NaN; 
    } 
    double avg = data[0]; 
    double sum = 0; 
    for ( int i = 1; i < data.length; i++ ){ 
      avg += data[i];
    } 
    
    return avg/n; 
  }

  public static double standardDeviation ( int[] data ) { 
    int n = data.length; 
    if ( n < 2 ){ 
      return Double.NaN; 
    } 
    double avg = data[0]; 
    double sum = 0; 
    for ( int i = 1; i < data.length; i++ ){ 
      double newavg = avg + ( data[i] - avg ) / ( i + 1 ); 
      sum += ( data[i] - avg ) * ( data [i] -newavg ) ; 
      avg = newavg; 
    } 
    return Math.sqrt( sum / n ); 
  }
  
  /**The A-star heuristic value of a city
   * 
   * @param ci
   * @param player
   * @return 
   */
  public int a_star_dest(City ci, int player){
      int out = 0, next = 0;
      City cityTo;
      //for each rail connected to this city
      for(Rail ri : getRailMapping(ci)){
        if(ri != null){
        next = ri.getScore();
        if (null == ri.player[0]){//rail is available IGNORES SECOND RAIL OPTION, two player only
            cityTo = getCityTo(ri,ci);
            for(Player p_player : cityTo.player){
                next = next * freedom_factor(ci);
            }
            next = next * destination_factor(cityTo);
            next += longestRoute_factor(cityTo, player);
            out += next;
        }
        
      }
      //get the points value of each connecting rail -- aggregate score as city value
      //if there is a player at the connected city, multiply rail score by DegoFreedomFactor
      //multiply by DestinationFactor
      //add LongestRouteFactor
      }
      return out;
      
  }
  
  
  /**The A-star heuristic value of a city
   * 
   * @param ci
   * @param player
   * @return 
   */
  public int a_star_dest_all(City ci, int player){
      int out = 0, next;
      City cityTo;
      //for each rail connected to this city
      for(Rail ri : getRailMapping(ci)){
        next = ri.getScore();
            cityTo = getCityTo(ri,ci);
            for(Player p_player : cityTo.player){//could even add in scale factors on opponent's score
              next = next * freedom_factor(ci);
            }
            next = next * destination_factor(cityTo);
            next += longestRoute_factor(cityTo, player);
        out += next;
      }
      //get the points value of each connecting rail -- aggregate score as city value
      //if there is a player at the connected city, multiply rail score by DegoFreedomFactor
      //multiply by DestinationFactor
      //add LongestRouteFactor
      
      return out;
  }
  
  /**A - Star Heuristic
   * 
   * @param city
   * @return 
   */
  public int freedom_factor(City city){
    //calculate the current degree of availability
    
    ArrayList<City[]> con_list = new ArrayList<City[]>(); 
    
    Player[] player_list = new Player[city.maxDegree];
    Rail[] rail_list = new Rail[city.maxDegree];
    int i = 0, deg_count = 0, player_count = 2;
    
    for(City[] ci : connections.keySet()){
      for(City cj : ci){
        if(cj == city){
          con_list.add(ci);
        }
      }
    }
    
    
    for(City[] ci : con_list){
      Rail r = connections.get(ci);
      rail_list[i] = r;
      i++;
    }
    
    for(Rail ri : rail_list){
      if(ri.player[0] != null){
        deg_count++;
      }
      
 /*     if(ri.player[0] != null){
        if(player_list[ri.player[0].playerID] == null){
          player_count++;
          player_list[ri.player[0].playerID] = ri.player[0];
        }
        //else nothing needs to be done since we've already seen this player and counted them
      }      
      */
    }
    city.currentDegree = city.maxDegree - deg_count;
    
    return (player_count/ city.currentDegree);
  }
  
   /**returns highest a-star weighted scoring city path between any two cities
  * 
  * @param pair
  * @return 
  */
 public City[] find_best_score(City[] pair, int AIPlayer){
    City current = pair[0];
    City destination = pair[1];
    Rail best = new Rail();
    ArrayList<City> open_c = new ArrayList<City>();
    ArrayList<Rail> closed_r = new ArrayList<Rail>();
    ArrayList<City> out = new ArrayList<City>();
    
    Map<City,City>from_list = new HashMap<City,City>();
    int visit_count = 0;
    Map<City, Integer> distance = new HashMap<City, Integer>();
    int dist_temp, heuristic_factor = 0;
    
    
    
    open_c.add(pair[0]);
    distance.put(pair[0], new Integer(0));
    
    
    while(!open_c.isEmpty()){
      
      
      current = open_c.get(0);
      dist_temp = distance.get(current);
      
      if(current == destination){
        if(visit_count < destination.maxDegree){
          visit_count++;
        }
        else{
          return (City[]) construct_path_score(from_list,current,out,distance).toArray();
        }
      }
      
      //GET NEIGHBORS
      Rail[] next_rail = getRailMapping(current);
      //FIND BEST NEIGHBOR
      for(Rail ri : next_rail){
        heuristic_factor = a_star_dest_all(getCityTo(ri,current), AIPlayer);
         
          
        if (best == null){
          best = ri;
        }
        else if(best.distance < ri.distance){//chooses longest route to maximize score
          best = ri;
        }
        
        //check if best is in closed list
        if(!closed_r.contains(best)){
          current = getCityTo(best,current);

        }
      //best choice was in closed list, check if distance is shorter
        else if (ri.distance * heuristic_factor < distance.get(getCityTo(best, current))){
          current = getCityTo(ri,current);
          best = ri;
        }
      }//find best
      
      for(Rail next_r : next_rail){
        if(!closed_r.contains(next_r)){
//          closed_r.add(next_r);
          for(City next_city : getCityAt(next_r)){
            if(next_city != current){//ADD H calculation
              heuristic_factor = a_star_dest(getCityTo(next_r,current), AIPlayer);
              distance.put(next_city, new Integer(dist_temp + next_r.distance * heuristic_factor));//longer paths are preffered
              from_list.put(next_city, current);
              open_c.add(next_city);
            }
          }//next city pair
        }//if best rail is not in closed
      }      
    }//while
    return new City[0];
  }
    
 
  /**Returns true if within the rails list, there exists a connection between the two cities
   * 
   * @param pair
   * @param owned
   * @return boolean, if the rails create a connection between these two cities
   */
  public boolean connection_exist(City[] pair, ArrayList<Rail> owned){
    City current = pair[0];
    City destination = pair[1];
    Rail best = new Rail();
    ArrayList<City> open_c = new ArrayList<City>();
    ArrayList<Rail> closed_r = new ArrayList<Rail>();
    ArrayList<City> out = new ArrayList<City>();
    
    Map<City,City>from_list = new HashMap<City,City>();
    int visit_count = 0;
    Map<City, Integer> distance = new HashMap<City, Integer>();
    int dist_temp = 0;
    boolean start = false, end = false;
    
    for(Rail rx  : owned ){
        City[] temp = getCityAt(rx);
        if(temp[0] == pair[0] || temp[1] == pair[0]){
            start = true;
        }
        if(temp[0] == pair[1] || temp[1] == pair[1]){
            end = true;
        }
    }
    
    if(start && end){
        
     
    open_c.add(pair[0]);
    distance.put(pair[0], new Integer(0));
    
    
    while(!open_c.isEmpty()){
      
      
      current = open_c.get(0);
      dist_temp = distance.get(current);
      
      if(current == destination){
          return true;
      }
      
      //GET NEIGHBORS
      Rail[] next_rail = getRailMapping(current);
      //FIND BEST NEIGHBOR
         
      
      
      for(Rail ri : next_rail){
        //if this rail is not in the list of rails we own
        if(!owned.contains(ri)){
            continue;
        }  
          
        if (best == null){
          best = ri;
        }
        else if(best.distance > ri.distance){//chooses shortest distance
          best = ri;
        }
        
        //check if best is in closed list
        if(!closed_r.contains(best)){
          current = getCityTo(best,current);

        }
      //best choice was in closed list, check if distance is shorter
        else if (dist_temp+1 < distance.get(getCityTo(best, current))){
          current = getCityTo(best,current);
        }
      }//find best
      
      for(Rail next_r : next_rail){
        if(!closed_r.contains(next_r)){
//          closed_r.add(next_r);
          for(City next_city : getCityAt(next_r)){
            if(next_city != current){
              distance.put(next_city, new Integer(dist_temp+1));
              from_list.put(next_city, current);
              open_c.add(next_city);
            }
          }//next city pair
        }//if best rail is not in closed
    
    }//while
  }
    }
    else{
        return false;
    }
    return false;
  }
 
 /**returns shortest city path between any two cities
  * 
  * @param pair
  * @return 
  */
 public City[] find_shortest_path(City[] pair){
    City current = pair[0];
    City destination = pair[1];
    Rail best = new Rail();
    ArrayList<City> open_c = new ArrayList<City>();
    ArrayList<Rail> closed_r = new ArrayList<Rail>();
    ArrayList<City> out = new ArrayList<City>();
    
    Map<City,City>from_list = new HashMap<City,City>();
    int visit_count = 0;
    Map<City, Integer> distance = new HashMap<City, Integer>();
    int dist_temp;
    
    
    
    open_c.add(pair[0]);
    distance.put(pair[0], new Integer(0));
    
    
    while(!open_c.isEmpty()){
      
      
      current = open_c.get(0);
      dist_temp = distance.get(current);
      
      if(current == destination){
        if(visit_count < destination.maxDegree){
          visit_count++;
        }
        else{
          return (City[]) construct_path(from_list,current,out).toArray();
        }
      }
      
      //GET NEIGHBORS
      Rail[] next_rail = getRailMapping(current);
      //FIND BEST NEIGHBOR
      for(Rail ri : next_rail){
        if (best == null){
          best = ri;
        }
        else if(best.distance > ri.distance){//chooses shortest distance
          best = ri;
        }
        
        //check if best is in closed list
        if(!closed_r.contains(best)){
          current = getCityTo(best,current);

        }
      //best choice was in closed list, check if distance is shorter
        else if (dist_temp+1 < distance.get(getCityTo(best, current))){
          current = getCityTo(best,current);
        }
      }//find best
      
      for(Rail next_r : next_rail){
        if(!closed_r.contains(next_r)){
//          closed_r.add(next_r);
          for(City next_city : getCityAt(next_r)){
            if(next_city != current){
              distance.put(next_city, new Integer(dist_temp+1));
              from_list.put(next_city, current);
              open_c.add(next_city);
            }
          }//next city pair
        }//if best rail is not in closed
      }      
    }//while
    return new City[0];
  }
 
 /**Returns the list of Rails that connects two cities
  * 
  * @return 
  */
 public ArrayList<Rail> get_Rail_Path(City ci, City cj){
     ArrayList<Rail> out = new ArrayList<Rail>();
     City[] pair = {ci,cj};

     City[] city_path = find_shortest_path(pair);
     
     for(int i = 0; i < city_path.length - 1; i++){
         out.add(getRailMappingAt(city_path[i],city_path[i+1]));
     }
     
     return out;
     
 }
 
  public ArrayList<City> construct_path(Map<City, City> from_list, City current, ArrayList<City> out){
    
    if(from_list.containsKey(current)){
     out = construct_path(from_list, from_list.get(current), out);

     out.add(out.size(), current);

     return out;
    }
    
    else{
      out.add(out.size(),current);
      return out;
    }
  }
  
  public ArrayList<City> construct_path_score(Map<City, City> from_list, City current, ArrayList<City> out, Map<City, Integer> score){
    
    if(from_list.containsKey(current)){
     out = construct_path_score(from_list, from_list.get(current), out, score );

     out.add(out.size(), current);
     
     out.get(0).player_temp_value = score.get(current);
     
     return out;
    }
    
    else{
      out.add(out.size(),current);
      return out;
    }
  }
  
  /**Calculates if the city will increase the longest route of a player.
   * Using a breakdown in quartiles by stdev (+- 1,2,3,4) & mean.
   * The closer to average your longest route is, the worse off you are, so 
   * value and desirability are negatively correlated. Since A* chooses the 
   * lower weighted neighbor first. The quartile value is scaled by degree of freedom
   * and destination factors.
   * 
   * @param city
   * @param player
   * @return
   */
  public int longestRoute_factor(City city, int player){
    //need list of player objects
    
    int[] player_length = new int[player_list.size()];
    int i = 0;
    double l_stdev, l_mean;
    
    for(Player pi : player_list){
      player_length[i] = pi.longest_route_cities.length;
      if(isConnected(city, pi.longest_route_cities) == 0){
        //take ave & stdev of players route length
        //multiply Stdev bound (+-1,2,3...) by destination & freedom
        l_stdev = standardDeviation(player_length);
        l_mean = mean(player_length);
        
        
        if(player_list.get(player).longest_route_cities.length < l_mean + l_stdev && player_list.get(player).longest_route_cities.length > l_mean){
          return -1 * destination_factor(city) * freedom_factor(city);
        }
        else if(player_list.get(player).longest_route_cities.length < l_mean + 2* l_stdev && player_list.get(player).longest_route_cities.length > l_mean){
          return -2 * destination_factor(city) * freedom_factor(city);
        }
        else if(player_list.get(player).longest_route_cities.length < l_mean + 3 * l_stdev && player_list.get(player).longest_route_cities.length > l_mean){
          return -3 * destination_factor(city) * freedom_factor(city);
        }
        else if(player_list.get(player).longest_route_cities.length > l_mean){
          return -4 * destination_factor(city) * freedom_factor(city);
        }
        
        if(player_list.get(player).longest_route_cities.length > l_mean + l_stdev && player_list.get(player).longest_route_cities.length < l_mean){
          return 1 * destination_factor(city) * freedom_factor(city);
        }
        else if(player_list.get(player).longest_route_cities.length > l_mean + 2* l_stdev && player_list.get(player).longest_route_cities.length < l_mean){
          return 2 * destination_factor(city) * freedom_factor(city);
        }
        else if(player_list.get(player).longest_route_cities.length > l_mean + 3 * l_stdev && player_list.get(player).longest_route_cities.length < l_mean){
          return 3 * destination_factor(city) * freedom_factor(city);
        }
        else if(player_list.get(player).longest_route_cities.length < l_mean){
          return 4 * destination_factor(city) * freedom_factor(city);
        }
        
        
      }
    }
    return 1;
  }
  
  /**Has a slightly different definition of 'connected'
   * Returns 0 if the city will increase the longest_route of a player
   * Otherwise returns smallest distance of connection to the route
   * 
   * @param q_city
   * @param route
   * @return
   */
  public int isConnected(City q_city, City[] route){
    int[] dist_city = new int[route.length];
    int i = 0;
    
    ArrayList<City[]> end_cities = new ArrayList<City[]>();
    end_cities.addAll(getCityMapping(route[0]));
    
    for(City[] pair :end_cities ){
      if(pair[0] == q_city || pair[1] == q_city){
        return 0;
      }
    }
    
    
    for(City r_city : route){
      dist_city[i] = shortest_distance(route, r_city);
    }
    for(int dist : dist_city){
      if(dist > 0){
        return dist;
      }
    }
    return -1;
  }
  
  /**G(x) - the path already taken
   * 
   * @return a normalized evaluation
   */
  public int a_star_prev(City[] path, int AIPlayer){
    //since I took this path, what happened?
    //play strategies: longest, destination, block
    // Longest - does anyone have a rail >= my length? weight by number of total rails available
    // Destination - how feasible is this destination? how many degrees of freedom exist between it & my closest position?
    // Block - curtail an opponent
      
    Player p = player_list.get(AIPlayer);
    int score_path = 0, next;
    
    
    for(int i = 0; i < path.length-1 ; i++){
        City ci = path[i];
        City cj = path[i+1];
        
        next = a_star_dest(ci, AIPlayer);
        next = next * destination_factor(ci);
        next = next * freedom_factor(ci);
        next += longestRoute_factor(ci, AIPlayer);
        
        next = next * getRailMappingAt(ci,cj).distance;
        if(i == path.length - 2){//at end of list, need to include final destination
            score_path +=next;
            next = a_star_dest(cj, AIPlayer);
            next = next * destination_factor(cj);
            next = next * freedom_factor(cj);
            next += longestRoute_factor(cj, AIPlayer);
            
            
        }
        score_path += next;
    }
        
    return score_path;
  }
  

  /**Calculates the possible outcomes, and returns the most favored. This will be called by the player object to provide the AI's decision for the given player.
   * 
   * @param player
   * @return the actual change in the player's score
   */
  
  public int choose_your_destiny(Player player){
      
    ArrayList<Integer> city_score = new ArrayList<Integer>();
    ArrayList<City[]> paths_eval = new ArrayList<City[]>();
    ArrayList<Rail> wanted_rails = new ArrayList<Rail>();
    City[] most_wanted_city;
    Rail can_has_rail = null;
    
    
    int best_index = 0, counti = 0;
    //run each possibility
    //A) draw two rail cards (from deck or face up)
    //B) claim a rail
    //C) draw three destination cards, keep two
    //choose optimal
    
      //HOW
      //check possible score change through taking a rail
      //if destinations are complete(or can be), check total trains left, determine if draw new destinations
     for(City cx : Cities){
         city_score.add(a_star_dest(cx,player.playerID));
     }
     
     for(Integer scorei : city_score){
         if(city_score.get(best_index) > scorei ){
             best_index = counti;
         }
         counti++;
     }
     
     for(City cp : player.cities_owned){
         //for each city in players list
         //determine the best path to take to that city
         //select most desired path
         //select rail on that path
         City[] temp = find_best_score(new City[]{cp,Cities[best_index]}, player.playerID);
         
         //Cant work at beginning of game, no cities/routes owned!
         paths_eval.add(temp);
         //paths_eval.add(new City[]{Denver});
                    
     }
     while(can_has_rail == null){
        best_index = 0;
        for(City[] path : paths_eval){
            if(paths_eval.get(best_index)[0].player_temp_value < path[0].player_temp_value){
                best_index = counti;
            }
            counti++;
        }

        //best_index NOW is most desired path
        //get the rails along the path we want. 
        //select a rail that is possible to use from the player's standpoint
        most_wanted_city = paths_eval.get(best_index);

        for(int i = 0; i < most_wanted_city.length - 1; i++ ){
            wanted_rails.addAll(get_Rail_Path(most_wanted_city[i], most_wanted_city[i+1]));
        }

        for(Rail rx : wanted_rails){
           if(rx.distance <= player.getHand().getHandColorsMap().get(rx.getColor_c())){
               //THIS IS THE RAIL WE ARE LOOKING FOR
               can_has_rail = rx;
           }
        }
     
     }
     //repeat until possibility is found    
     //then see how many points that rail will give us THAT is the determining factor between which option to pick
     //the change in points a selecting a rail will incur is also the return value
     //if a highly desired move isn't found, search the board for a card that matches a highly desired route
     //if none are found draw from deck OR draw from destination pile
     
     int pointChange = can_has_rail.getScore();
     
     //take ave & stdev of players route length
    //multiply Stdev bound (+-1,2,3...) by destination & freedom
     
    int[] player_scores = new int[player_list.size()];
     
     for(int i =0; i < player_list.size(); i++){
         player_scores[i] = player_list.get(i).score;
     }
     
     
    double l_stdev_pre = standardDeviation(player_scores);
    double l_mean_pre = mean(player_scores);
    
    int preQuartile = quartileStdDev(l_mean_pre, l_stdev_pre, player.score);
    
    
    player_scores[player.playerID] = player.score + pointChange;
    
    double l_stdev_post = standardDeviation(player_scores);
    double l_mean_post = mean(player_scores);

    int postQuartile = quartileStdDev(l_mean_post, l_stdev_post, player.score+pointChange);
    
    if(postQuartile - preQuartile > 0){//increased our avg by atleast one stdDev
        //DO IT RETURN
    } 
    else if(postQuartile - preQuartile == 0){//maintains status quo
        //are there any cards on the board we REALLY WANT?
        
       for(int more_wanted = 0; more_wanted < best_index; more_wanted++){
           //need rail color & distance
           COLOR[] want_color = wanted_rails.get(more_wanted).getColor_c();
           int distance = wanted_rails.get(more_wanted).distance;
           
           //number trains on the board will create a complete set that i actually want more than the set i could get
           if(tickettoride.getSlotColorsMap().get(want_color) >= (distance - (int)player.hand.getHandColorsMap().get(want_color))){
               //PICK THOSE CARDS RETURN
           }
           
        }//THESE ARE NOT THE CARDS I'M LOOKING FOR
                
        //check game state to determine if more destination cards could be drawn
       //for each destination set a player has
       //calculate % of completion on each set
     
       
       int[] trains = new int[player_list.size()];
       
       for(int i = 0; i < player_list.size(); i++){
           trains[i] = player_list.get(i).available_trains;
       }
       //... && mean(trains) > (total possible trains minus scale factor of log(total max score/current score)*fudge factor
       if(player.hand.destComplete(wanted_rails) && mean(trains) > (45 - (45 * Math.log(290/l_mean_pre)*.75))){
           //DRAW FROM DESTINATION PILE
           //PICK BEST TWO
           //RETURN
       }
       
       //otherwise RANDOM TakeRail or DrawFromDeck
       Random rand = new Random();
       //as train cards increases, probability of drawing them decreases
       double trainCardProportion = rand.nextInt(player.hand.numTrainCards())+1 * (1/(player.hand.numTrainCards()+1));
       
       if(rand.nextDouble() < trainCardProportion ){
           //TAKE THE TRAIN CARD FROM DECK
       }
       else{
           //Take the rail anyway
       }
                   
    }
    else{//should always be non-negative since a score can only increase, the stdDevquartile difference will always be atleast 0     
    }
      return 0;
  }
   
  public int quartileStdDev(double l_mean, double l_stdev, int query){
    if(query < l_mean + l_stdev && query > l_mean){
      return 1;
    }
    else if(query < l_mean + 2* l_stdev && query > l_mean){
      return 2;
    }
    else if(query < l_mean + 3 * l_stdev && query > l_mean){
      return 3;
    }
    else if(query > l_mean){
      return 4;
    }
    
    if(query > l_mean - l_stdev && query < l_mean){
      return -1;
    }
    else if(query > l_mean + 2* l_stdev && query < l_mean){
      return -2;
    }
    else if(query > l_mean + 3 * l_stdev && query < l_mean){
      return -3;
    }
    else{
      return -4;
    }
    
    
  }
  
  
  /**Returns the rail connecting two cities, null if two cities are not adjacent
   * 
   * @param city_i
   * @return
   */
  public Rail getRailMappingAt(City city_i,City city_j){
    Rail out = null;
    int i = 0;
    
    for(City[] ci : connections.keySet()){
      if(ci[0] == city_i && ci[1] == city_j || ci[0] == city_j && ci[1] == city_i){
        out = connections.get(ci);
      }
    }
    return out;
  }
  
  
  /**The operational equivalent of an edgelist.
   * 
   * @param city
   * @return list of rails that connect with city 
   */
  public Rail[] getRailMapping(City city){
    Rail[] out = new Rail[city.maxDegree]; 
    int i = 0;
    
    for(City[] ci : connections.keySet()){
      if(ci[0].name == city.name || ci[1].name == city.name){
        out[i] = connections.get(ci);
        
        i++;//out is the only variable depending on i
      }
     
    }
    return out;
  }
  
  
  /**Equivalent to getCityAt, but returns only the destination
   * 
   * @param rail
   * @param from
   * @return
   */
  
  public City getCityTo(Rail rail, City from){
    for(Entry<City[], Rail> en :connections.entrySet()){
      if(rail == en.getValue()){
        for(City c : en.getKey()){
          if(c != from){
            return c;
          }
        }
      }
    }
    return null;
  }
  
  /**Gives you the pair of cities that a rail connects
   * @param rail
   * @return City[] connected pair
   */
  
  public City[] getCityAt(Rail rail){
    for(Entry<City[], Rail> en :connections.entrySet()){
      if(rail == en.getValue()){
        return en.getKey();
      }
    }
      return null;
  }
 
  /**The operational equivalent of a nextlist 
   * 
   * @param city
   * @return list of map keys (city pairs) to all rails that connect with city 
   */
  public ArrayList<City[]> getCityMapping(City city){
    ArrayList<City[]> out = new ArrayList<City[]>();
    int i = 0;
    
    for(City[] ci : connections.keySet()){
      if(ci[0] == city || ci[1] == city){
        out.add(ci);
        
        i++;
      }
    }
    return out;
  }
  
}
